1. Field of the Invention
Methods and apparatuses consistent with the present invention relate to a video encoding method and apparatus and a video decoding method and apparatus, and more particularly, to a video encoding method and apparatus and a video decoding method and apparatus in which a processing order for predetermined-size blocks included in a macroblock is defined in order to efficiently use spatial correlation in an image.
2. Description of the Related Art
In the H.264/Moving Picture Experts Group (MPEG)—4 Advanced Video Coding (AVC) encoder/decoder (CODEC) standard, video data is compressed by performing a prediction process on sample data in block units in order to obtain a prediction block composed of prediction samples, and then, transforming and quantizing the prediction block.
Two methods are used for the prediction process: intraprediction and interprediction. Interprediction involves performing motion compensation/estimation with reference to a reference picture that has passed through an encoding/decoding process, and deblocking filtering. Intraprediction is performed on a current picture using data of neighboring blocks that are previously encoded. Video data compressed through a prediction process and a transformation and quantization process is compressed again through an entropy coding process to become a bitstream conforming to the H.264/AVC standard.
FIG. 1 illustrates prediction modes in the H.264/AVC standard according to division of a macroblock and a sub-macroblock.
In FIG. 1, various prediction modes classified according to a macroblock division type for interprediction are shown. According to the H.264/AVC standard, the available prediction modes are a 16×16 prediction mode, an 8×16 prediction mode, a 16×8 prediction mode, and an 8×8 prediction mode. Also, according to the H.264/AVC standard, the available prediction modes according to division of a sub-macroblock are a 4×8 prediction mode, an 8×4 prediction mode, and a 4×4 prediction mode.
Interprediction can be performed in those 7 prediction modes. For example, in the 8×8 prediction mode, motion compensation and motion prediction are performed on each of four 8×8 blocks included in a macroblock in order to generate a motion-compensation prediction value for each 8×8 block. In this case, each 8×8 block may further be divided into 4×4 blocks for motion compensation and motion prediction. In motion compensation and motion prediction, blocks obtained by dividing a macroblock are subject to motion compensation and motion prediction sequentially in the order illustrated in FIG. 1.
Once a residue between a prediction block obtained by motion compensation and motion prediction and a block corresponding to an original image is calculated, the residue passes through transformation and quantization. In the H.264/AVC standard, transformation and quantization are performed on the residue in 4×4 block units.
FIG. 2 illustrates a related art order of processing 4×4 blocks when transformation and quantization of a residue are processed in 4×4 block units in prediction modes according to the H.264/AVC standard.
Referring to FIG. 2, residues generated by motion compensation and motion prediction using one of 16×16, 16×8, 8×16, 8×8, 8×4, 4×8, and 4×4 blocks pass through transformation and quantization in 4×4 block units according to an order illustrated in FIG. 2. For example, after motion compensation and motion prediction are performed in 16×8 block units, transformation and quantization are performed in 4×4 block units according to the order illustrated in FIG. 2 for a residue between a prediction block of each 16×8 block and an original input block.
According to the related art order of processing 4×4 blocks for transformation and quantization, even after motion compensation and motion prediction are completed for some blocks obtained by dividing a macroblock, 4×4 block-based transformation and quantization for a residue are performed in a fixed processing order regardless of a macroblock division type. As a result, a motion compensation and motion prediction processing order is not consistent with a transformation/quantization processing order and thus a synchronous block process may not be possible for some macroblock division types. For example, referring to FIG. 2, when a macroblock 21 is divided into two 8×16 blocks 21a and 21b for motion compensation and motion prediction, the left 8×16 block 21a is motion-compensated and motion-predicted before the right 8×16 block 21b. However, in transformation and quantization, the lower 4×4 residues in the left 8×16 block 21a are processed 8th, 9th, 10th, and 11th after upper 4×4 residues in the right 8×16 block 21b are processed 4th, 5th, 6th, and 7th. Similarly, when an 8×8 block 23 is divided into two 4×8 blocks 23a and 23b for motion compensation and motion prediction, the left 4×8 block 23a is motion-compensated and motion-predicted before the right 4×8 block 23b, but lower 4×4 residues in the left 4×8 block 23a are transformed and quantized after upper 4×4 residues of the right 4×8 block 23b. 
As such, according to this related art, in the case of some macroblock division types, even if motion compensation and motion prediction of a block are completed, subsequent processing of the block, e.g., transformation, quantization, and deblocking filtering, can be performed only after processing of other blocks is completed.
Moreover, when spatial correlation between a current block to be encoded and neighboring blocks thereof is used, data of the neighboring blocks may not be properly used due to non-completion of processing of the data of the neighboring blocks according to some macroblock division types.